#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/7/25 13:06
# @USER    : Shengji He
# @File    : SplitArrayLargestSum.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List


class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        """
        Given an array which consists of non-negative integers and an integer m, you can split the array
        into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

        Note:

        If n is the length of array, assume the following constraints are satisfied:
            - 1 ≤ n ≤ 1000
            - 1 ≤ m ≤ min(50, n)
        Examples:
            Input:
                nums = [7,2,5,10,8]

                m = 2
            Output:
                18

        Explanation:
        There are four ways to split nums into two subarrays.

        The best way is to split it into [7,2,5] and [10,8],

        where the largest sum among the two subarrays is only 18.

        :param nums:
        :param m:
        :return:
        """
        num_sum = sum(nums)
        return self.__split(nums, m, num_sum)

    def __split(self, nums: List[int], m: int, num_sum: int) -> int:
        if m == 1:
            return num_sum
        min_sum = num_sum / m
        sum1 = 0
        n = len(nums)
        for i in range(n):
            if sum1 + nums[i] < min_sum:
                sum1 += nums[i]
            else:
                min_other1 = self.__split(nums[i:], m-1, num_sum-sum1)
                rlt1 = max(min_other1, sum1)
                sum1 = sum1+nums[i]
                if sum1 < rlt1 and i < n-1:
                    min_other2 = self.__split(nums[i+1:], m-1, num_sum-sum1)
                    rlt2 = max(min_other2, sum1)
                    return min(rlt1, rlt2)
                else:
                    return rlt1


if __name__ == '__main__':
    S = Solution()
    nums = [7, 2, 5, 10, 8]
    m = 2
    # nums = [2,3,1,2,4,3]
    # m = 5
    print(S.splitArray(nums, m))

    print('done')
